/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/generate-parentheses
   @Language: C++
   @Datetime: 19-03-20 09:42
   */

class Solution {
	void core(int i, int j, int n, string &str, vector<string> &vs){
		if (i<n){
			str[i+j]='(';
			core(i+1,j,n,str,vs);
		}
		if (j<n && j<i){
			str[i+j]=')';
			core(i,j+1,n,str,vs);
		}
		if (i==n && j==n) vs.push_back(str);
	}

public:
	/**
	 * @param n: n pairs
	 * @return: All combinations of well-formed parentheses
	 */
	vector<string> generateParenthesis(int n) {
		// write your code here
		if (n<1) return {""};
		string str(n*2,'(');
		vector<string> vs;
		core(0,0,n,str,vs);
		return vs;
	}
};
